package kyssion.leetcode.num1_50;

import java.util.Arrays;
import java.util.Comparator;

public class code11_盛最多水的容器 {
    /**
     * 普通方法 n^2
     *
     * @param height
     * @return
     */
    public int maxArea1(int[] height) {
        return 1;
    }

    /**
     * nlog(n)+1 排序方法
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        Item[] items = new Item[height.length];
        for (int a = 0; a < height.length; a++) {
            Item item = new Item();
            item.value = height[a];
            item.index = a;
            items[a] = item;
        }
        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o1.value - o2.value;
            }
        });
        int[] needMax = new int[height.length];
        Arrays.fill(needMax, -1);
        int maxIndex = Integer.MIN_VALUE;
        int minIndex = Integer.MAX_VALUE;
        int maxM = Integer.MIN_VALUE;
        for (int a = items.length - 1; a >= 0; a--) {
            minIndex = Math.min(items[a].index, minIndex);
            maxIndex = Math.max(items[a].index, maxIndex);
            int way = Math.max(Math.abs(items[a].index - minIndex), Math.abs(items[a].index - maxIndex));
            maxM = Math.max(items[a].value * way, maxM);
        }
        return maxM;
    }

    class Item {
        int value;
        int index;
    }

    /**
     * 优化算法 高级贪心优化,还是找规律的问题,截肢到了极限了
     *  找规律核心就是当right的大小大于left的时候,将会导致最大值就是这个位置
     *
     * @param height
     * @return
     */
    public int maxArea3(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left <= right) {
            while (left <= right) {
                if (height[left] <= height[right]) {
                    max = Math.max(height[left] * (right - left), max);
                    break;
                }
                max = Math.max(height[right] * (right - left), max);
                right--;
            }
            left++;
        }
        return max;
    }

}
